JZ57 二叉树的下一个结点

https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

第一次解

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
      public TreeLinkNode GetNext(TreeLinkNode pNode) {
          // 1.
          if (pNode.right != null) {
              TreeLinkNode pRight = pNode.right;
              while (pRight.left != null) {
                  pRight = pRight.left;
              }
              return pRight;
          }
          // 2.
          if (pNode.next != null && pNode.next.left == pNode) {
              return pNode.next;
          }
          // 3.
          if (pNode.next != null) {
              TreeLinkNode pNext = pNode.next;
              while (pNext.next != null && pNext.next.right == pNext) {
                  pNext = pNext.next;
              }
              return pNext.next;
          }
          return null;
      }
}

这题主要讲下思路

其实画个图就很好理解了，就是在第二次递归序的时候打印，其它两次不打印

如下：

      1              
  2      3      
4  5    6   7

每次只执行第二次

1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1
      ^   ^   ^     ^     ^   ^   ^

所以最后打印顺序是：
4 2 5 1 6 3 7

情况一：当前节点存在右节点，那么返回的则是它右边的最左节点，例如这里的 1 节点，下一个节点是 6，

情况二：如果它没有右节点（例如 6），则判断上一层的节点，如果当前是左节点则直接返回当前节点的上一级就行了

情况三：无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。（例如 5）

情况三画个图会比较清晰：

如图：i 的下一个节点是 b

注意，这里取得最左节点使用的是迭代，而不是递归